// 思路：设定左右节点为数组两端，取两个节点中心位置mid，比较mid处的值与target的大小，如果相等返回mid，
// 否则，如果该值小于target，将左节点设置为mid+1，如果该值大于target，将右节点设置为mid-1


// 左闭右闭
function search(nums, target) {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// 时间复杂度Ologn
// 空间复杂度O1

let arr = [1, 3, 4, 7, 8, 9]
console.log(search(arr, 7))

// 左闭右开
function search2(nums, target) {
    let left = 0
    let right = nums.length
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return -1
}

console.log(search2(arr, 7))